Given pointer to the head node of a linked list, the task is to reverse the linked list. We need to reverse the list by changing the links between nodes.
Input: Head of following linked list
1->2->3->4->NULL
Output: Linked list should be changed to,
4->3->2->1->NULL
Iterative Method
START-->Initialize three pointers prev as NULL, curr as head and next as NULL ----> Iterate through the linked list. In loop, do following.
// Before changing next of current,// store next node.
next = curr->next
// Now change next of current.// This is where actual reversing happens
curr->next = prev
// Move prev and curr one step forward
prev = curr
curr = next
coding--->
class LinkedList {
static Node head;
static class Node {
int data;
Node next;
Node(int d)
{
data = d;
next = null;
}
}
/* Function to reverse the linked list */
Node reverse(Node node)
{
Node prev = null;
Node current = node;
Node next = null;
while (current != null) {
next = current.next;
current.next = prev;
prev = current;
current = next;
}
node = prev;
return node;
}
// prints content of double linked list
void printList(Node node)
{
while (node != null) {
System.out.print(node.data + " ");
node = node.next;
}
}
// Driver Code
public static void main(String[] args)
{
LinkedList list = new LinkedList();
list.head = new Node(85);
list.head.next = new Node(15);
list.head.next.next = new Node(4);
list.head.next.next.next = new Node(20);
System.out.println("Given Linked list");
list.printList(head);
head = list.reverse(head);
System.out.println("");
System.out.println("Reversed linked list ");
list.printList(head);
}
}
Time Complexity: O(n)
Auxiliary Space: O(1)
another approach
This operation is a thorough one. We need to make the last node to be pointed by the head node and reverse the whole linked list.
First, we traverse to the end of the list. It should be pointing to NULL. Now, we shall make it point to its previous node −
We have to make sure that the last node is not the last node. So we'll have some temp node, which looks like the head node pointing to the last node. Now, we shall make all left side nodes point to their previous nodes one by one.
Except the node (first node) pointed by the head node, all nodes should point to their predecessor, making them their new successor. The first node will point to NULL.
We'll make the head node point to the new first node by using the temp node.
The linked list is now reversed.
Recursive Method:
- Divide the list in two parts - first node and rest of the linked list.
- Call reverse for the rest of the linked list.
- Link rest to first.
- Fix head pointer
coding--->
class recursion {
static Node head; // head of list
static class Node {
int data;
Node next;
Node(int d)
{
data = d;
next = null;
}
}
static Node reverse(Node head)
{
if (head == null || head.next == null)
return head;
/* reverse the rest list and put
the first element at the end */
Node rest = reverse(head.next);
head.next.next = head;
/* tricky step -- see the diagram */
head.next = null;
/* fix the head pointer */
return rest;
}
/* Function to print linked list */
static void print()
{
Node temp = head;
while (temp != null) {
System.out.print(temp.data + " ");
temp = temp.next;
System.out.println();
}
static void push(int data)
{
Node temp = new Node(data);
temp.next = head;
head = temp;
}
/* Driver program to test above function*/
public static void main(String args[])
{
/* Start with the empty list */
push(20);
push(4);
push(15);
push(85);
System.out.println("Given linked list");
print();
head = reverse(head);
System.out.println("Reversed Linked list");
print();
}
}
Output:
Given linked list
85 15 4 20
Reversed Linked list
20 4 15 85
Time Complexity: O(n)
Auxiliary Space: O(n)
Home